{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #数字游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numsGame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数字游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小扣在秋日市集入口处发现了一个数字游戏。主办方共有 `N` 个计数器，计数器编号为 `0 ~ N-1`。每个计数器上分别显示了一个数字，小扣按计数器编号升序将所显示的数字记于数组 `nums`。每个计数器上有两个按钮，分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器，按下加一或减一按钮。\n",
    "\n",
    "主办方请小扣回答出一个长度为 `N` 的数组，第 `i` 个元素(0 <= i < N)表示将 `0~i` 号计数器 **初始** 所示数字操作成满足所有条件 `nums[a]+1 == nums[a+1],(0 <= a < i)` 的最小操作数。回答正确方可进入秋日市集。\n",
    "\n",
    "由于答案可能很大，请将每个最小操作数对 `1,000,000,007` 取余。\n",
    "\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`nums = [3,4,5,1,6,7]`\n",
    ">\n",
    ">输出：`[0,0,0,5,6,7]`\n",
    ">\n",
    ">解释：\n",
    ">i = 0，[3] 无需操作\n",
    ">i = 1，[3,4] 无需操作；\n",
    ">i = 2，[3,4,5] 无需操作；\n",
    ">i = 3，将 [3,4,5,1] 操作成 [3,4,5,6], 最少 5 次操作；\n",
    ">i = 4，将 [3,4,5,1,6] 操作成 [3,4,5,6,7], 最少 6 次操作；\n",
    ">i = 5，将 [3,4,5,1,6,7] 操作成 [3,4,5,6,7,8]，最少 7 次操作；\n",
    ">返回 [0,0,0,5,6,7]。\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`nums = [1,2,3,4,5]`\n",
    ">\n",
    ">输出：`[0,0,0,0,0]`\n",
    ">\n",
    ">解释：对于任意计数器编号 i 都无需操作。\n",
    "\n",
    "**示例 3：**\n",
    ">输入：`nums = [1,1,1,2,3,4]`\n",
    ">\n",
    ">输出：`[0,1,2,3,3,3]`\n",
    ">\n",
    ">解释：\n",
    ">i = 0，无需操作；\n",
    ">i = 1，将 [1,1] 操作成 [1,2] 或 [0,1] 最少 1 次操作；\n",
    ">i = 2，将 [1,1,1] 操作成 [1,2,3] 或 [0,1,2]，最少 2 次操作；\n",
    ">i = 3，将 [1,1,1,2] 操作成 [1,2,3,4] 或 [0,1,2,3]，最少 3 次操作；\n",
    ">i = 4，将 [1,1,1,2,3] 操作成 [-1,0,1,2,3]，最少 3 次操作；\n",
    ">i = 5，将 [1,1,1,2,3,4] 操作成 [-1,0,1,2,3,4]，最少 3 次操作；\n",
    ">返回 [0,1,2,3,3,3]。\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `1 <= nums.length <= 10^5`\n",
    "- `1 <= nums[i] <= 10^3`\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [5TxKeK](https://leetcode.cn/problems/5TxKeK/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [5TxKeK](https://leetcode.cn/problems/5TxKeK/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,4,5,1,6,7]', '[1,2,3,4,5]', '[1,1,1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsGame(self, nums: List[int]) -> List[int]:\n",
    "        c = nums.pop(0) + 1#递增序列当前值\n",
    "        s = [0]#差值排序列表\n",
    "        res = [0]\n",
    "        pre = 0#对应之前代码的sum(s[mid:]) - sum(s[:mid])\n",
    "        for i, n in enumerate(nums):\n",
    "            l = i + 2\n",
    "            mid = (i + 1) // 2#中位数下标\n",
    "            idx = bisect.bisect_left(s, n - c)#新元素所在位置\n",
    "            s.insert(idx, n - c)\n",
    "            if i % 2 == 0:#当列表从奇数变为偶数，中位数位置不变\n",
    "                if idx > mid:#如果新元素在中位数右侧，只需要加上新元素其他不变\n",
    "                    pre += n - c\n",
    "                else:#当新元素在中位数左侧，原来的中位数右移，本来是减法现在是加法，所以要加上两倍的原来中位数，新元素在左侧，需要减去\n",
    "                    pre += 2 * s[mid + 1] - (n - c)\n",
    "            else:#当列表从偶数变为奇数，中位数位置+1\n",
    "                if idx > mid:#当新元素在右侧，由于中位数位置+1，原来做加法的元素需要减去两倍，并加上新元素\n",
    "                    pre += n - c - s[mid] * 2\n",
    "                else:#当新元素在左侧时，原来的中位数已经向右顺移一位，没有变化，减去新元素即可\n",
    "                    pre -= (n - c)\n",
    "            res.append(pre + (mid + 1) * s[mid] - (l - mid - 1) * s[mid])\n",
    "            c += 1\n",
    "            res[-1] %= 10 ** 9 + 7\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "class Solution:\n",
    "    mod = 1000000007\n",
    "\n",
    "    def numsGame(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        \n",
    "        for i in range(n):\n",
    "            nums[i] -= i\n",
    "        \n",
    "        q0, q1 = [-min(nums[0], nums[1])], [max(nums[0], nums[1])]\n",
    "        sum0, sum1 = -q0[0], q1[0]\n",
    "        ans = [0, int(sum1 - sum0) % self.mod]\n",
    "\n",
    "        for i in range(2, n):\n",
    "            if nums[i] <= -q0[0]:\n",
    "                heappush(q0, -nums[i])\n",
    "                sum0 += nums[i]\n",
    "            else:\n",
    "                heappush(q1, nums[i])\n",
    "                sum1 += nums[i]\n",
    "            \n",
    "            if len(q0) == len(q1) + 2:\n",
    "                u = -heappop(q0)\n",
    "                sum0 -= u\n",
    "                heappush(q1, u)\n",
    "                sum1 += u\n",
    "            elif len(q0) + 1 == len(q1):\n",
    "                u = heappop(q1)\n",
    "                sum1 -= u\n",
    "                heappush(q0, -u)\n",
    "                sum0 += u\n",
    "            \n",
    "            delta = sum1 - sum0 + (-q0[0] if not i & 1 else 0)\n",
    "            ans.append(delta % self.mod)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def numsGame(self, nums: List[int]) -> List[int]:\n",
    "        nums = [nums[i] - i for i in range(len(nums))]\n",
    "        left_heap = []  #左侧为大根堆\n",
    "        right_heap = [] #右侧为小根堆\n",
    "        median = nums[0]\n",
    "        sl = 0\n",
    "        sr = 0\n",
    "        ret = [0] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            if i%2 == 0:\n",
    "                #左右堆大小相等，现要再加入一元素\n",
    "                left_root = -left_heap[0]\n",
    "                right_root = right_heap[0]\n",
    "                if nums[i] < left_root:\n",
    "                    median = left_root\n",
    "                    heapq.heapreplace(left_heap, -nums[i])#由于heaqp是小根堆，存相反数来实现大根堆\n",
    "                    sl = sl -left_root + nums[i]\n",
    "                elif nums[i] > right_root:\n",
    "                    median = right_root\n",
    "                    heapq.heapreplace(right_heap, nums[i])\n",
    "                    sr = sr - right_root + nums[i]\n",
    "                else:\n",
    "                    median = nums[i]\n",
    "\n",
    "            else:\n",
    "                if nums[i] > median:\n",
    "                    heapq.heappush(right_heap, nums[i])\n",
    "                    heapq.heappush(left_heap, -median)\n",
    "                    sl += median\n",
    "                    sr += nums[i]\n",
    "                else:\n",
    "                    heapq.heappush(left_heap,-nums[i])\n",
    "                    heapq.heappush(right_heap,median)\n",
    "                    sl += nums[i]\n",
    "                    sr += median\n",
    "            ret[i] = (sr - sl)%1000000007\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsGame(self, nums: List[int]) -> List[int]:\n",
    "        MOD = 10**9+7\n",
    "        n = len(nums)\n",
    "\n",
    "        import heapq\n",
    "\n",
    "        nums = [nums[i]-i for i in range(n)]\n",
    "        # print(nums)\n",
    "        left_heap = []\n",
    "        right_heap = []\n",
    "\n",
    "        sl = 0\n",
    "        sr = 0\n",
    "\n",
    "        median = nums[0]\n",
    "\n",
    "        ret = [0]*n\n",
    "\n",
    "        for i in range(n):\n",
    "            print(median)\n",
    "            len_left, len_right = len(left_heap), len(right_heap)\n",
    "            # print(len_left, len_right)\n",
    "\n",
    "            if len_left==len_right:\n",
    "                # print(1)\n",
    "                # left_root = -left_heap[0] if len_left>0 else float(\"inf\")\n",
    "                if nums[i] <= median:\n",
    "                    heapq.heappush(left_heap, -nums[i])\n",
    "                    sl = (sl + nums[i])%MOD\n",
    "                    len_left += 1\n",
    "                else:\n",
    "                    heapq.heappush(right_heap, nums[i])\n",
    "                    sr = (sr+nums[i])%MOD\n",
    "                    len_right += 1\n",
    "            \n",
    "            elif len_left<len_right:\n",
    "                # print(2)\n",
    "                # left_root = -left_heap[0] if len_left>0 else float(\"inf\")\n",
    "                if nums[i]<=median:\n",
    "                    heapq.heappush(left_heap, -nums[i])\n",
    "                    sl = (sl+nums[i])%MOD\n",
    "                else:\n",
    "                    heapq.heappop(right_heap)\n",
    "                    heapq.heappush(right_heap, nums[i])\n",
    "                    heapq.heappush(left_heap, -median)\n",
    "                    sl = (sl+median)%MOD\n",
    "                    sr = (sr+nums[i] - median)%MOD\n",
    "                len_left += 1\n",
    "            \n",
    "            else:\n",
    "                # print(3)\n",
    "                # right_root = right_heap[0] if len_right>0 else -float(\"inf\")\n",
    "                if nums[i]>=median:\n",
    "                    heapq.heappush(right_heap, nums[i])\n",
    "                    sr = (sr+nums[i])%MOD\n",
    "                else:\n",
    "                    heapq.heappop(left_heap)\n",
    "                    heapq.heappush(left_heap, -nums[i])\n",
    "                    heapq.heappush(right_heap, median)\n",
    "                    sl = (sl+nums[i] - median)%MOD\n",
    "                    sr = (sr+median)%MOD\n",
    "                len_right += 1\n",
    "\n",
    "            if len_left>len_right:\n",
    "                median = -left_heap[0]\n",
    "            else:\n",
    "                median = right_heap[0]\n",
    "                \n",
    "            ret[i] = ((median*(len_left-len_right))%MOD-sl+sr)%MOD\n",
    "\n",
    "            # print(nums[i], left_heap, right_heap, median,  sl, sr, ret[i])\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numsGame(self, nums: List[int]) -> List[int]:\n",
    "        n, minf, mod = len(nums), 0, 10 ** 9 + 7\n",
    "        res, L, R = [], [float(\"inf\")], [float(\"inf\")]\n",
    "        for i in range(n):\n",
    "            a = nums[i]\n",
    "            minf += max(0, -L[0] + i - a)\n",
    "            heapq.heappush(R, -heapq.heappushpop(L, -a + i))\n",
    "            minf += max(0, a - R[0] - i)\n",
    "            heapq.heappush(L, -heapq.heappushpop(R, a - i))\n",
    "            res.append(minf % mod)\n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
